# 填充
# 10001?0001 -> 1000110001(3) -> 1000100001(3)
# 1??0001 -> 1100001(3)
# 10?1?0 -> 100110(2)

from leetcode import test_function as tf


def get_pairs_num(inp_str: str):
    """我的方法, 超时/总数=2/20"""
    res = 0
    while inp_str:
        if len(inp_str) == 1:  # 如果长度为1, 则直接返回
            return res
        if inp_str[0] != inp_str[1] and inp_str[0] != "?" and inp_str[1] != "?":  # 如果两个数字不相同, 且没有?, 抛弃首位
            inp_str = inp_str[1:]
        else:
            if inp_str[0] == inp_str[1] == "1" or inp_str[0] == inp_str[1] == "0":  # 两个数字相同, 且没有?, 结果+1,抛弃前两位
                res += 1
                inp_str = inp_str[2:]
            elif inp_str[0] == "?" and (inp_str[1] == "1" or inp_str[1] == "0"):  # 首位为? 次位为数字, 结果+1, 抛弃前两位
                res += 1
                inp_str = inp_str[2:]
            elif inp_str[1] == "?" and (inp_str[0] == "1" or inp_str[0] == "0"):  # 首位为数字 次位为?, 结果+1, 抛弃前两位
                res += 1
                inp_str = inp_str[2:]
            elif inp_str[0] == inp_str[1] == "?":  # 两个?, 结果+1, 抛弃前两位
                res += 1
                inp_str = inp_str[2:]

    return res


def get_pairs_num_opt(inp_str: str):
    """主要优化:
    1. 截取字符串这个过程需要消耗大量时间, 这里使用指针cursor代替
    2. 大量的逻辑可以省略
    """
    cursor, n = 0, len(inp_str)
    if len(inp_str) == 1:  # 如果长度为1, 则直接返回
        return 0
    res = 0
    while cursor < n - 1:
        # 如果两个数字不相同, 且没有?, 抛弃首位
        if inp_str[cursor] != inp_str[cursor + 1] and inp_str[cursor] != "?" and inp_str[cursor + 1] != "?":
            cursor += 1
        else:
            res += 1
            cursor += 2

    return res


if __name__ == '__main__':
    # inp = input()

    with open("../../data/2023_c.in", "r") as file:
        str = file.readline().replace('\n', '')
    inp = [{"inp_str": "10001?0001"},
           {"inp_str": "1??0001"},
           {"inp_str": "10?1?0"},
           {"inp_str": str}, ]
    out = [3, 3, 2, 428813]
    tf(get_pairs_num, inp, out)
    tf(get_pairs_num_opt, inp, out)
